// tree.c
// 二叉搜素树
# include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
    int data;           // 数据域
    struct Node *left;  // 左子树
    struct Node *right; // 右子树
} Node;

Node* insert(Node *root, int val);
void pre_order(Node *root);
//二叉搜索树 中序遍历就是从小到大的顺序
void in_order(Node *root);
void post_order(Node *root);

int main()
{
    //根节点的指针
    Node *root = NULL;
    root = insert(root, 42);
    root = insert(root, 9);
    root = insert(root, 72);
    root = insert(root, 32);
    root = insert(root, 17);

    in_order(root);
    return 0;
}

Node *insert(Node *root, int val)
{
    //如果为空树
    if(root == NULL)
    {
        root = malloc(sizeof(Node));
        root->data = val;
        root->left = NULL;
        root->right = NULL;
        return root;
    }
    //小于当前节点值，插入左子树
    if(val < root->data)
    {
        root->left = insert(root->left, val);
    }
    //大于等于节点值，插入右子树
    if(root->data < val)
    {
        root->right = insert(root->right, val);
    }
    return root;
}

void in_order(Node *root)
{
    if(root == NULL)
        return;
    in_order(root->left);       //先中序输出左子树
    printf("%d ", root->data);   //打印根节点
    in_order(root->right);      //再中序打印右子树
}

void pre_order(Node *root)
{
    if(root == NULL)
        return;
    printf("%d", root->data);   //先打印根
    pre_order(root->left);      //左
    pre_order(root->right);     //右
}

